package BackTrackingPackage2;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Lzm
 * @version 1.0
 */
public class partition_ {
  List<List<String>> result = new ArrayList<>();
  List<String> list = new ArrayList<>();

  @Test
  public void partitionTest(){
    String s = "aab";
    List<List<String>> partition = partition(s);
    for (List<String> strings : partition) {
      System.out.println(strings);
    }
  }

  public List<List<String>> partition(String s) {
    backTracking(s,0,new StringBuilder());
    return result;
  }

  public void backTracking(String s,int startIndex,StringBuilder sb){
    if (startIndex >= s.length()){
      result.add(new ArrayList<>(list));
      return;
    }
    for (int i = startIndex ; i < s.length() ; i++){
      sb.append(s.charAt(i));
      if (check(sb)){
        list.add(sb.toString());
        backTracking(s,i+1,new StringBuilder());
        list.remove(list.size() - 1);
      }
    }
  }
  private boolean check(StringBuilder sb){
    for (int i = 0; i < sb.length()/ 2; i++){
      if (sb.charAt(i) != sb.charAt(sb.length() - 1 - i)){return false;}
    }
    return true;
  }
}
